package leecode;
/**
 * 题目：基于时间戳的键值对存储
 * 方法：哈希表存储+二分查找 为实现 get 操作，我们需要用一个哈希表存储 set操作传入的数据。
 * 具体地，哈希表的键为字符串key，值为一个二元组列表，二元组中存储的是时间戳timestamp 和值 value。
 * 
 * 由于set操作的时间戳都是严格递增的，因此二元组中保存的时间戳也是严格递增的，这样可以根据
 * get操作中的key在哈希表中找到对应的二元组pairs，然后根据timestamp在pairs中二分查找。找到比timestamp
 * 小的时间戳里面最大的时间戳，因此可以二分找到第一个超过timestamp中的二元组下标，否则，二元组不存在， 返回空字符串。
 */

//! 做算法题，需要用到复杂的容器类，还是java更好用；python适合刷一些纯逻辑的算法题，一旦涉及到容器类，java可用的包很多
import java.util.Map;
import java.util.List;
import java.util.ArrayList;
import java.util.HashMap;

class TimeMap {
    // 二元组定义，也是一个类
    class Pair implements Comparable<Pair> {
        int timestamp;
        String value;

        public Pair(int timestamp, String value) {
            this.timestamp = timestamp;
            this.value = value;
        }

        public int hashCode() {
            return timestamp + value.hashCode();
        }

        public boolean equals(Object obj) {
            if (obj instanceof Pair) {
                Pair pair2 = (Pair) obj;
                return this.timestamp == pair2.timestamp && this.value.equals(pair2.value);
            }
            return false;
        }

        public int compareTo(Pair pair2) {
            if (this.timestamp != pair2.timestamp) {
                return this.timestamp - pair2.timestamp;
            } else {
                return this.value.compareTo(pair2.value);
            }
        }
    }

    Map<String, List<Pair>> map;

    // 构造函数
    public TimeMap() {
        map = new HashMap<String, List<Pair>>();
    }

    // set函数
    public void set(String key, String value, int timestamp) {
        List<Pair> pairs = map.getOrDefault(key, new ArrayList<Pair>());
        pairs.add(new Pair(timestamp, value));
        map.put(key, pairs);
    }

    // get函数
    public String get(String key, int timestamp) {
        List<Pair> pairs = map.getOrDefault(key, new ArrayList<Pair>());
        // 使用一个大于所有 value 的字符串，以确保在 pairs 中含有 timestamp 的情况下也返回大于 timestamp 的位置
        Pair pair = new Pair(timestamp, String.valueOf((char) 127));
        int i = binarySearch(pairs, pair);
        if (i > 0) {
            return pairs.get(i - 1).value;
        }
        return "";
    }

    // 二分查找
    private int binarySearch(List<Pair> pairs, Pair target) {
        int low = 0, high = pairs.size() - 1;
        if (high < 0 || pairs.get(high).compareTo(target) <= 0) {
            return high + 1;
        }
        while (low < high) {
            int mid = (high - low) / 2 + low;
            Pair pair = pairs.get(mid);
            if (pair.compareTo(target) <= 0) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
}
